COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASB30\M3NGR25\M4NGR20\M5NGB30\M6BASI30\F2\CSTANFORD UNIVERSITY
C00027 ENDMK
C⊗;
\\M1BASL30;\M2BASB30;\M3NGR25;\M4NGR20;\M5NGB30;\M6BASI30;\F2\CSTANFORD UNIVERSITY
\F3\CSTANFORD, CALIFORNIA 94305
\F4COMPUTER SCIENCE DEPARTMENT\←L\-R\/'7;\+R\→.\→S   Telephone:
\←S\→.415-497-4971
\F1\CJan 9, 1975





\CCurriculum '68 Considered Harmful
\Cor
\CDon't look at trees until you've seen the forest.




Robert L. Ashenhurst, ACM Editor-in-Chief
Institute for Computer Research
The University of Chicago
Chicago, Ill.  60637


Dear Dr. Ashenhurst:

\JPerhaps this letter should be addressed to the SIGCSE instead of to the
membership at large, but I feel that education is the business of the
whole community. 
The letter addresses itself particularly to the undergraduate educational
policies.
The general thesis of these remarks is that a fundamental
restructuring of \F6Curriculum 68\F1
is long overdue. 
In particular the beginning courses,
which will make or break a department, must reflect a more unified look at the
field of Computer Science giving the new student motivation and perspective.
Unless a beginning student can be convinced that Computer Science
is something other than programming or hardware, then he becomes easy prey
for other departments. As presently constituted, Curriculum 68 does little
to dispell  such doubts. It is my belief that much of the fault lies in the
data structures course, I1. 

Too many colleges and universities have slavishly copied
the I1-Data Structures description without proper regard for the importance
of its place in the 68-graph. 
In many universities, I1 is the first \F6real\F1 computer science course.
The previous courses are computing courses, covering basic programming
and perhaps hardware and finite mathematics. The difficulty is that such a background
does not adequately prepare a student for the usual dose of I1.  
All too frequently  this course
deals too much with tricks and techniques and too little with ideas and
motivation. 
It is not that the content of I1 is difficult; the problem is motivation.
Other than a possible interest in toy problems
or a desire to please the instructor, why should a student with such a meager
background be  interested in data structures?

Once you start down the path,  questioning the
content of I1, other doubts arise. Why use machine language to describe 
data structures? We don't require machine language for courses on numerical analysis 
so why not treat data structures with the same respect?
So nominally, what one desires is a high level language which  can be used to
describe data structure algorithms. 

On further reflection we might also think about the courses which will follow I1
and what we can do to prepare the student for them. We should, if possible,
prepare students for courses on translator construction,
for systems programming, for a more theoretical
course on correctness, structured programming, programming methodology and 
all those other funny little words.
Can we motivate these later courses by giving additional care to the
preparation of I1? I believe the answer is  yes.
While teaching at UCLA in 1970-1972 I developed  an alternative approach based on
LISP.
LISP is an excellent way to take intelligent but technically naive students rapidly
to advanced topics in such a way that a coherent picture of much of
modern computer science is presented.
I shall now attempt to justify this rather dogmatic position.

First we address the problems of motivating the current content of I1.
What was the \F6original\F1 motivation for these techniques of data structuring? 
The  tricks and techniques arose from real needs of programmers working
on increasingly sophisticated projects. Though they arose from diverse
problem areas, many  arose in the context of language implementation; and
the \F6ideas\F1 to be presented in I1 can all be handled in a discussion
such an implementation.
Now interjecting language implementation into our discussion seems like
a step backwards. Before anyone should undertake such a project he must
have a clear understanding of all of the details of the language. 
We hope to present a convincing argument that, with the proper choice
of language, this approach is natural and within reach of the beginning student.

What language should we pick? Many exist and any, from
machine language to high level language, could be used.
For a course in the position of I1 we also want a language which we can use to
talk about data structures at some level of abstraction.
We are first interested in motivating the ideas, not in bit-pushing and efficiency.
So we would like a high level language suitable for describing data structures
and their manipulations; we will talk about the techniques  of I1 
when we discuss implementation of the language and
need to understand the issues of representation of data structures and the
mechanization of data-structure algorithms.
The language we pick for I1 should also be  \F6real\F1. There is a certain soothing
effect on the student if he knows that he is not the subject in some
ill-conceived language design experiment.
Many languages still meet these requirements. LISP is just one.
True, many of the techniques first arose in solving the problems of implementation
of LISP, but historical precedence is not sufficient motivation for picking
a language.
To understand the importance of LISP for I1 and succeeding courses we must
look deeper.

Let's start from the basics.
LISP meta-expressions are syntactically quite simple so that the students
soon become proficient in its glories. 
Most students have sufficient sophistication to understand recursion;  indeed
most are quite impressed with the power of recursion over symbolic expressions.
When teaching programming style, we can introduce McCarthy's ideas of
abstract syntax (which have recently surfaced as abstract data structures)
and can say as much as anyone can about structured programming, by discussing
the importance of separating  data structures from their representation.
When introducing λ-binding, call-by-value, functional arguments and recursion,
we introduce the problems of symbol tables and environments.

LISP's rather unique approach of mapping language expressions onto data structures
thus opening the door to an interpreter definition of semantics gives a rapid
and precise description of implementation.
Once that implementation is digested the natural question is implementation on a \F6real\F1
machine.
This real  implementation gives added insights into the problems of data structures.
introducing garbage collection, linked allocation,  and symbol table manipulation.

Given a real machine and an understanding of the LISP interpreter, it is
easy to introduce compilers. Indeed there is no easier way to describe compilation
than in the context of LISP.
One of the side effects of this approach is to show that compilers really
are quite simple programs and, as far as the understanding of a language is 
concerned, are not very interesting. Thus the course on compiler construction
should give more time to the  techniques of interpreter construction and
the general problems of language design.

So that the more theoretical-minded participant does not feel slighted, we
can speak of correctness and equivalence of LISP programs. And if we
feel ambitious, we can even enter the realm of Scott's logic and introduce
denotational models of LISP subsets.

For the applications programmer we need only cite fifteen years of
most interesting artificial intelligence programs or clever compilers, or
advanced interactive debuggers or editors, all written in LISP.
Thus LISP  is not a toy language but has a rich history of interesting
programming examples. 

Once the ideas involved in data structure manipulation are seen in a
rich environment like LISP, we can easily motivate questions about efficiency.
LISP's structure-modifying functions show some of the difficulties; examining 
LISP's implementation motivates questions of alternative representations and alternative
storage control regimes.

Finally, for the more speculative-minded, we can show throughout our LISP discussions
that there are difficulties and defects in the original design.
Armed with fifteen years experience with LISP, and language design in general, it is
reasonably simple to propose revisions to LISP.

Perhaps this seems like a lot for a beginning student. 
It has turned out not to be the case. Either students are a lot smarter than
we give them credit for, or this approach through a study of the layers of 
LISP is an important approach.
This use of LISP did not spring forth full-sized from its creator; five
classes of students suffered through the birth pangs.
At the last UCLA manifestation
the undergraduates got everything but the applications and the theory.
Since that time I have extended the approach to include an even more unified
approach to data structures.
At  the University of California Santa Cruz Graduate Workshop the
students got the same dose in a week.  And in the spring semester
at San Jose State University their graduate students will get everything.
Thus depending on the time and the students, the approach can be fast or slow,
introductory or research.

So where are we? 
I have claimed the most of the content of I1 is very naturally motivated
by courses which come \F6after\F1 I1.  I have claimed that we need a course
to bridge the gap between computing courses and computer science courses.
Just what are we advocating? 
Our initial sortie into
data structures has turned into a course on language design and
just about everything else.  
What we claim then, is that the 68-graph isn't just out-of date, it's wrong.
The presentation we are advocating isn't new; all but a few of the ideas 
are present in McCarthy's earliest work; all these papers were available in 1968.
McCarthy is not even mentioned in the bibliography attached to I1!
What is normally taught as
a course on data structures, does not belong at 
a point like I1 in the ACM graph. 
The typical student's background just is
not sufficient to support this approach.  
Such a course would have value later in the student's career when
problems of efficiency have relevance.
But I1 should be a feeder course for 
courses on translater construction, systems programming, semantics of programming
languages, and the rest of the courses in the department. The computer science
major
must get a realistic overview of the  field and the interested bystander
must be tantalized into joining the ranks.

Though I have advocated  restructuring of the undergraduate curriculum for
many years, a recent sequence of events finally precipitated this letter.
First, two letters appeared in a recent issue of SIGACT Notices,
where some of our more theoretical colleagues are advocating similar changes.
Though I am in agreement with most of their remarks, I find it somewhat
surprising that the criticism first comes from this quarter. I do not consider
my approach to data structures as inherently theoretical. It lends itself
equally to exploitation by the realist. Perhaps the  programming language
practitioners are just more reticent.

Concurrently, I had begun preparation for a new data structures course and
had found that the same rather stale diet of programming classes was being used
to introduce data structures. I had talked with people about my opinions on
data structures and found the pros and cons equally divided as to the
adequacy of my approach. I was particularly surprised to see 
a number of respected people among the cons (no pun intended).
I had read a recent issue of SIGCSE dealing with
revisions to Curriculum 68.
The net effect of these inputs was rather discouraging and I began to
wonder why a field as dynamic as computer science is still advocating
such uninspired courses.  The obvious and immediate answer is that
computer science is like any other field; teaching is not a respectable
profession. That's a bit too easy. I think  a better answer comes from the
history of the field. Computer science departments usually were
outgrowths of either mathematics or engineering departments. 
Now hardware courses require a reasonable background in \F6real\F1
engineering and physics. But what \F6real\F1 background do you need to
be a programmer? The usual answer was "none". And that's where the problems
started. The typical department then justified its existence by 
offering programming classes, supplying cannon fodder for other departments
and for industry.
Now computing classes most certainly should be taught by computer scientists;
we need only look at secondary schools and high schools to see what
happens when subjects are  presented by people without adequate background.
But the departments must go beyond this image of a service bureau. They must
outgrow this  feeling of inadequacy; they should become less sensitive to
the immediate needs of industry and stop confusing dispensation of 
technical skill with education.
The departments must be willing to do a lot more missionary work.
The discipline is not in a sufficiently well-defined stage that we
can be dispensers of conventional wisdom; we should be advocating
how things \F6should be\F1 rather than pontificating about how things \F6are\F1.
Dijkstra's \F6Humble Programmer\F1 should be required reading.

Perhaps my approach smacks of elitism; I claim not so. I claim that many, if
not all, of the
current difficulties  hiding under the blanket of \F6The Software Problem\F1
are traceable to poorly trained programmers. I claim that we must expect
professional programmers to be as sophisticated as their engineering or mathematical
counterparts. 
Indeed, many people have noted that if the practitioners in other technical fields
performed in the cavalier manner of current programming methodology, the death
toll would be enormous.
The violence done by poor programming is not so visible but is at least as severe.
The problems in current programming practice are not those of efficiency
but are those of \F6correctness\F1.
People write buggy programs.
Faster machines will not solve these problems;
faster machines or automatic programming systems will not 
overcome poorly educated programmers. I reiterate: these remarks are directed
toward undergraduate education; graduate students should know how to
take care of themselves. Other technical departments expect their undergraduates 
to become conversant with the basic tools of the discipline. The basic tools
of computer science are not programming languages, \F6per se\F1, but are
the cultivation of methods of thought. It has been remarked that few programmers
discover recursion; they are told about it. That's a shame. 

There is a succinct statement by C. Strachey which reflects my attitude about
programming languages and therefore my approach to data structures:
	\F6"I always worked on programming languages because it seems to me that
until you could understand those, you couldn't understand computers. Understanding
them doesn't really mean only being able to use them. A lot of people can use them
without understanding them."\F1
\.
\←L\→S\←R\-L\/'2;\+L\→L

Yours sincerely,



John R. Allen 
Research Associate
Computer Science Dept
Artificial Intelligence Labs

\←S\→L